package com.cqs.leetcode;

import com.cqs.leetcode.ds.ArraysUtils;


/**
 * Created by cqs on 2018/4/8.
 */
public class HouseRobber {

    /**
     * 动态规划(DP)
     * 思路：
     *
     * 若抢劫第i家店 那么第i-1家就不能抢劫 cost[i] = cost[i - 2] + nums[i];
     * 若不抢劫第i家 那么cost[i] = cost[i-1]
     * 求抢至第i家店最大金额等价于cost[i] = Math.max(cost[i - 1], cost[i - 2] + nums[i]);
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        //表示抢至第i家店时的最大金额
        int[] cost = new int[nums.length];
        cost[0] = nums[0];
        cost[1] = Math.max(nums[0], nums[1]);
        int max = cost[1];
        for (int i = 2; i < nums.length; i++) {
            //状态转移方程
            cost[i] = Math.max(cost[i - 1], cost[i - 2] + nums[i]);
            if (cost[i] > max) {
                max = cost[i];
            }
        }
        return max;
    }


    public static void main(String[] args) {
        HouseRobber r = new HouseRobber();
        int[] data = ArraysUtils.randInts(10);
        ArraysUtils.print(data);
        System.out.println("最大金:" + r.rob(data));
    }
}
